package lcp.p7;

/**
 * @author: trtan
 * @date: 2021-07-01 09:28
 **/
public class ConveyInformation {
    /**
     * 给定一些相邻的边，求k步从0到n的方案数
     * 数据量不大，n最大只有10，于是暴力搜索求方案数
     * @param n
     * @param relation
     * @param k
     * @return int
     * @author trtan
     * @date 2021/7/1 9:41
     */
    public int numWays(int n, int[][] relation, int k) {
        int[][] edges = new int[n][n];
        for (int i = 0; i < relation.length; i++) {
            int x = relation[i][0];
            int y = relation[i][1];
            edges[x][y] = 1;
        }
        return dfs(edges, 0, 0, k, n - 1);
    }

    int dfs(int[][] edges, int now, int cnt, int k, int target) {
        if(cnt >= k) {
            if (now == target) {
                return 1;
            }
            return 0;
        }
        int ans = 0;
        for (int i = 0; i <= target; i++) {
            if (edges[now][i] == 1) {
                ans += dfs(edges, i, cnt + 1, k, target);
            }
        }
        return ans;
    }
}
